home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / elib-006.lha / elib-0.06 / library / dll-debug.el < prev    next >
Lisp/Scheme  |  1993-01-24  |  8KB  |  304 lines
  1. ;;; dll-debug -- A slow implementation of dll for debugging.
  2. ;;; $Id: dll-debug.el,v 1.7 1993/01/24 20:43:10 ceder Exp $
  3. ;;; Copyright (C) 1991,1992  Per Cederqvist
  4. ;;;
  5. ;;; This program is free software; you can redistribute it and/or modify
  6. ;;; it under the terms of the GNU General Public License as published by
  7. ;;; the Free Software Foundation; either version 2 of the License, or
  8. ;;; (at your option) any later version.
  9. ;;;
  10. ;;; This program is distributed in the hope that it will be useful,
  11. ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. ;;; GNU General Public License for more details.
  14. ;;;
  15. ;;; You should have received a copy of the GNU General Public License
  16. ;;; along with this program; if not, write to the Free Software
  17. ;;; Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.  
  20. ;;; This is a plug-in replacement for dll.el.  It is dreadfully
  21. ;;; slow, but it facilitates debugging.  Don't trust the comments in
  22. ;;; this file too much.
  23. (provide 'dll)
  24.  
  25. ;;;
  26. ;;; A doubly linked list consists of one cons cell which holds the tag
  27. ;;; 'DL-LIST in the car cell and the list in the cdr 
  28. ;;; cell. The doubly linked list is implemented as a normal list. You
  29. ;;; should use dll.el and not this package in debugged code. This
  30. ;;; package is not written for speed...
  31. ;;;
  32.  
  33. ;;; ================================================================
  34. ;;;      Internal functions for use in the doubly linked list package
  35.  
  36. (defun dll-get-dummy-node (dll)
  37.  
  38.   ;; Return the dummy node.   INTERNAL USE ONLY.
  39.   dll)
  40.  
  41. (defun dll-list-nodes (dll)
  42.  
  43.   ;; Return a list of all nodes in DLL.   INTERNAL USE ONLY.
  44.  
  45.   (cdr dll))
  46.  
  47. (defun dll-set-from-node-list (dll list)
  48.  
  49.   ;; Set the contents of DLL to the nodes in LIST.
  50.   ;; INTERNAL USE ONLY.
  51.  
  52.   (setcdr dll list))
  53.  
  54. (defun dll-get-node-before (dll node)
  55.   ;; Return the node in DLL that points to NODE. Use
  56.   ;; (dll-get-node-before some-list nil) to get the last node.
  57.   ;; INTERNAL USE ONLY.
  58.   (while (and dll (not (eq (cdr dll) node)))
  59.     (setq dll (cdr dll)))
  60.   (if (not dll)
  61.       (error "Node not on list"))
  62.   dll)
  63.  
  64. (defmacro dll-insert-after (node element)
  65.   (let ((node-v (make-symbol "node"))
  66.     (element-v (make-symbol "element")))
  67.     (` (let (((, node-v) (, node))
  68.          ((, element-v) (, element)))
  69.      (setcdr (, node-v) (cons (, element-v) (cdr (, node-v))))))))
  70.  
  71. ;;; ===================================================================
  72. ;;;       The public functions which operate on doubly linked lists.
  73.  
  74. (defmacro dll-element (dll node)
  75.  
  76.   "Get the element of a NODE in a doubly linked list DLL.
  77. Args: DLL NODE."
  78.  
  79.   (` (car (, node))))
  80.  
  81.  
  82. (defun dll-create ()
  83.   "Create an empty doubly linked list."
  84.   (cons 'DL-LIST nil))
  85.  
  86.  
  87. (defun dll-p (object)
  88.   "Return t if OBJECT is a doubly linked list, otherwise return nil."
  89.   (eq (car-safe object) 'DL-LIST))
  90.  
  91.  
  92. (defun dll-enter-first (dll element)
  93.   "Add an element first on a doubly linked list.
  94. Args: DLL ELEMENT."
  95.   (setcdr dll (cons element (cdr dll))))
  96.  
  97.  
  98. (defun dll-enter-last (dll element)
  99.   "Add an element last on a doubly linked list.
  100. Args: DLL ELEMENT."
  101.   (dll-insert-after (dll-get-node-before dll nil) element))
  102.  
  103.  
  104. (defun dll-enter-after (dll node element)
  105.   "In the doubly linked list DLL, insert a node containing ELEMENT after NODE.
  106. Args: DLL NODE ELEMENT."
  107.  
  108.   (dll-get-node-before dll node)
  109.   (dll-insert-after node element))
  110.  
  111.  
  112. (defun dll-enter-before (dll node element)
  113.   "In the doubly linked list DLL, insert a node containing ELEMENT before NODE.
  114. Args: DLL NODE ELEMENT."
  115.  
  116.   (dll-insert-after (dll-get-node-before dll node) element))
  117.  
  118.  
  119.  
  120. (defun dll-next (dll node)
  121.   "Return the node after NODE, or nil if NODE is the last node.
  122. Args: DLL NODE."
  123.  
  124.   (dll-get-node-before dll node)
  125.   (cdr node))
  126.  
  127.  
  128. (defun dll-previous (dll node)
  129.   "Return the node before NODE, or nil if NODE is the first node.
  130. Args: DLL NODE."
  131.  
  132.   (let ((prev (dll-get-node-before dll node)))
  133.     (if (eq dll prev)
  134.     nil
  135.       prev)))
  136.  
  137.  
  138. (defun dll-delete (dll node)
  139.  
  140.   "Delete NODE from the doubly linked list DLL.
  141. Args: DLL NODE. Return the element of node."
  142.  
  143.   (setcdr (dll-get-node-before dll node) (cdr node))
  144.   (car node))
  145.  
  146.  
  147. (defun dll-delete-first (dll)
  148.  
  149.   "Delete the first NODE from the doubly linked list DLL.
  150. Return the element. Args: DLL. Returns nil if the DLL was empty."
  151.  
  152.   (prog1
  153.       (car (cdr dll))
  154.     (setcdr dll (cdr (cdr dll)))))
  155.  
  156.  
  157. (defun dll-delete-last (dll)
  158.  
  159.   "Delete the last NODE from the doubly linked list DLL.
  160. Return the element. Args: DLL. Returns nil if the DLL was empty."
  161.  
  162.   (let* ((last (dll-get-node-before dll nil))
  163.      (semilast (dll-get-node-before dll last)))
  164.     (if (eq last dll)
  165.     nil
  166.       (setcdr semilast nil)
  167.       (car last))))
  168.  
  169.  
  170. (defun dll-first (dll)
  171.  
  172.   "Return the first element on the doubly linked list DLL.
  173. Return nil if the list is empty. The element is not removed."
  174.  
  175.   (car (cdr dll)))
  176.  
  177.  
  178.  
  179.  
  180. (defun dll-last (dll)
  181.  
  182.   "Return the last element on the doubly linked list DLL.
  183. Return nil if the list is empty. The element is not removed."
  184.  
  185.   (let ((last (dll-get-node-before dll nil)))
  186.     (if (eq last dll)
  187.     nil
  188.       (car last))))
  189.  
  190.  
  191.  
  192. (defun dll-nth (dll n)
  193.  
  194.   "Return the Nth node from the doubly linked list DLL.
  195.  Args: DLL N
  196. N counts from zero. If DLL is not that long, nil is returned.
  197. If N is negative, return the -(N+1)th last element.
  198. Thus, (dll-nth dll 0) returns the first node,
  199. and (dll-nth dll -1) returns the last node."
  200.  
  201.   ;; Branch 0 ("follow left pointer") is used when n is negative.
  202.   ;; Branch 1 ("follow right pointer") is used otherwise.
  203.  
  204.   (if (>= n 0)
  205.       (nthcdr n (cdr dll))
  206.     (unwind-protect
  207.     (progn (setcdr dll (nreverse (cdr dll)))
  208.            (nthcdr (- n) dll))
  209.       (setcdr dll (nreverse (cdr dll))))))
  210.  
  211. (defun dll-empty (dll)
  212.  
  213.   "Return t if the doubly linked list DLL is empty, nil otherwise"
  214.  
  215.   (not (cdr dll)))
  216.  
  217. (defun dll-length (dll)
  218.  
  219.   "Returns the number of elements in the doubly linked list DLL."
  220.  
  221.   (length (cdr dll)))
  222.  
  223.  
  224.  
  225. (defun dll-copy (dll &optional element-copy-fnc)
  226.  
  227.   "Return a copy of the doubly linked list DLL.
  228. If optional second argument ELEMENT-COPY-FNC is non-nil it should be
  229. a function that takes one argument, an element, and returns a copy of it.
  230. If ELEMENT-COPY-FNC is not given the elements are not copied."
  231.  
  232.   (if element-copy-fnc
  233.       (cons 'DL-LIST (mapcar element-copy-fnc (cdr dll)))
  234.     (copy-sequence dll)))
  235.  
  236.  
  237. (defun dll-all (dll)
  238.  
  239.   "Return all elements on the double linked list DLL as an ordinary list."
  240.  
  241.   (cdr dll))
  242.  
  243.  
  244. (defun dll-clear (dll)
  245.  
  246.   "Clear the doubly linked list DLL, i.e. make it completely empty."
  247.  
  248.   (setcdr dll nil))
  249.  
  250.  
  251. (defun dll-map (map-function dll)
  252.  
  253.   "Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
  254. The function is applied to the first element first."
  255.  
  256.   (mapcar map-function (cdr dll)))
  257.  
  258.  
  259. (defun dll-map-reverse (map-function dll)
  260.  
  261.   "Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
  262. The function is applied to the last element first."
  263.  
  264.   (unwind-protect
  265.       (setcdr dll (nreverse (cdr dll)))
  266.     (mapcar map-function (cdr dll))
  267.     (setcdr dll (nreverse (cdr dll)))))
  268.  
  269.  
  270. (defun dll-create-from-list (list)
  271.  
  272.   "Given an elisp LIST create a doubly linked list with the same elements."
  273.  
  274.   (cons 'DL-LIST list))
  275.  
  276.  
  277.  
  278. (defun dll-sort (dll predicate)
  279.  
  280.   "Sort the doubly linked list DLL, stably, comparing elements using PREDICATE.
  281. Returns the sorted list. DLL is modified by side effects.
  282. PREDICATE is called with two elements of DLL, and should return T
  283. if the first element is \"less\" than the second."
  284.  
  285.   (setcdr dll (sort (cdr dll) predicate))
  286.   dll)
  287.  
  288.  
  289. (defun dll-filter (dll predicate)
  290.  
  291.   "Remove all elements in the doubly linked list DLL for which PREDICATE
  292. return nil."
  293.  
  294.   (let* ((prev dll)
  295.      (node (cdr dll)))
  296.  
  297.     (while node
  298.       (cond
  299.        ((funcall predicate (car node))
  300.     (setq prev node))
  301.        (t
  302.     (setcdr prev (cdr node))))
  303.       (setq node (cdr node)))))
  304.